public class Solution5 {
    //97. 交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[m+1][n+1]; // 表示s1(0,i)，s2(0,j)是否能组成s3(0,i+j)

        s1 = "_" + s1;
        s2 = "_" + s2;
        s3 = "_" + s3;
        dp[0][0] = true;
        for (int i = 1; i < m+1; i++) {  // s2为空时
            if (s1.charAt(i) == s3.charAt(i)) {
                dp[i][0] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i < n+1; i++) {  // s1为空时
            if (s2.charAt(i) == s3.charAt(i)) {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                dp[i][j] = (s1.charAt(i) == s3.charAt(i+j) && dp[i-1][j])
                        || (s2.charAt(j) == s3.charAt(i+j) && dp[i][j-1]);
            }
        }
        return dp[m][n];

    }
}
